using System;
using System.IO;					// Zur Arbeit mit Datei
using System.Collections.Generic;	// Grundlegende Datenstrukturen

namespace Graph
{
	public class UndirectGraph
	{
        /*groesster Knoten Grad kann man wieder loeschen*/
        public int KnotenGrad = 0;

		// Anzahl der Kanten
		protected int m;
			
		// Liste der Knoten
        protected Dictionary<int, DijkstraKnoten> v;

        // ungerichtete Kanten :: Zugriff Start-Knoten ID -> Zugriff Ziel-Knoten ID -> Kante
        protected Dictionary<int, Dictionary<int,List<Kante>>> e;
		
		/// <summary>Standardkonstruktor</summary> 
        public UndirectGraph()
		{
			m = 0;
            v = new Dictionary<int,DijkstraKnoten>();
            e = new Dictionary<int, Dictionary<int,List<Kante>>>();
		}
	
		/// <summary>Methode zum Einfügen eines neuen Knotens</summary>
		/// <param name="id">ID des einzufügenden Knotens</param>
		/// <param name="daten">Daten am Knoten</param>
		public virtual void neuerKnoten(int id)
		{
            DijkstraKnoten Node = new DijkstraKnoten(id);
            v.Add(id, Node);
            e.Add(id, new Dictionary<int, List<Kante>>());
		}
        public virtual void neuerKnoten(DijkstraKnoten Node)
        {
            v.Add(Node.Id, Node);
            e.Add(Node.Id, new Dictionary<int, List<Kante>>());
        }
		
		/// <summary>Methode zum EInfügen einer neuen Kante (auch parallel).</summary>
		/// <param name="von">ID des Startknotens</param>
		/// <param name="nach">ID des Zielknotens</param>
		/// <param name="gewicht">Kantengewicht</param>
        public virtual void neueKante (int von, int nach, double gewicht)
        {
        	//if (von == nach)
        	//    throw new Exception(String.Format("Es sollte eine Schlinge von {0} nach {1} eingefügt werden! Graph unterstützt dies nicht!", von, nach));
        	Kante Edge1 = new Kante (von, nach, gewicht);
        	Kante Edge2 = new Kante (nach, von, gewicht);
        	if (e[von].ContainsKey (nach))
				e[von][nach].Add(Edge1);
            else
                e[von].Add(nach, new List<Kante>() {Edge1});

			if (von != nach)
			{
	            if (e[nach].ContainsKey(von))
	                e[nach][von].Add(Edge2);
	            else
	                e[nach].Add(von,new List<Kante> {Edge2});
			}
			m++;
        }
        public virtual void neueKante (Kante kante, double gewicht)
        {
        	//if (kante.Von == kante.Nach)
        	//    throw new Exception(String.Format("Es sollte eine Schlinge von {0} nach {1} eingefügt werden! Graph unterstützt dies nicht!", kante.Von, kante.Nach));
        	Kante Rueckwaertskante = new Kante (kante.Nach, kante.Von, kante.Gewicht);

            if (e[kante.Von].ContainsKey (kante.Nach))
        		e[kante.Von][kante.Nach].Add (kante);
        	else
        		e[kante.Von].Add (kante.Nach, new List<Kante> { kante });

			if (kante.Von != kante.Nach)
			{
        		if (e[kante.Nach].ContainsKey (kante.Von))
        			e[kante.Nach][kante.Von].Add (Rueckwaertskante);
        		else
        			e[kante.Nach].Add (kante.Von, new List<Kante> { Rueckwaertskante });
			}
			m++;
        }     		
		
		public virtual int N
		{
			get{return v.Count;}
		}
		public virtual int M
		{
			get{return this.m;}
		}
        public virtual Dictionary<int, DijkstraKnoten> V { get { return v; } }
        public Dictionary<int, Dictionary<int,List<Kante>>> E { get{return e;} }


        public bool loadDIMACS(string pfad)
        {
            /* DIMACS-Format :
            // Zeilen mit % am Anfang ignorieren
            // normalerweise n+1 unkommentierte Zeilen
            // 1. Zeile: n m (fmt) (conn)
            // fmt = 	0		gar keine Gewichte
            //			1		Kantengewichte	
            //			10		Knotengewichte
            //			11		Kanten- und Knotengewichte
            //			100 	Graph hat Schleifen und Mehrfach-Kanten
            // ncon =	Anzahl der Gewichte am Knoten
            // übrigen Zeilen im ungewichteten Fall: ungeordnete Adjazenzlisten für die Knoten 1 bis n
            */

            StreamReader datei = new StreamReader(pfad);
            
            string zeile;

            // 1. Zeile mit Parametern einlesen
            zeile = datei.ReadLine();
            while (zeile == "" || zeile[0] == '%')						// Leer- und Kommentarzeilen überspringen 
                zeile = datei.ReadLine();
            int temp_n = Convert.ToInt32(zeile.Split(' ')[0]);			// ermittle Anzahl der Knoten
            int temp_m = Convert.ToInt32(zeile.Split(' ')[1]);			// ermittle Anzahl der Kanten
            int temp_fmt = -1;											// Standardwert: keine Angabe zum Format
            int temp_ncon = -1;											// Standardwert: keine Angabe zur Anzhal der Knotengewichte
            if (zeile.Split(' ').Length > 2)
            {
                temp_fmt = Convert.ToInt32(zeile.Split(' ')[2]);		// ermittle Format-Einstellung
                if (zeile.Split(' ').Length > 3)
                    temp_ncon = Convert.ToInt32(zeile.Split(' ')[3]);	// ermittle Anzahl der Knotengewichte
            }

            // eingelesene Parameter anzeigen
            Console.WriteLine(temp_n + " " + temp_m + " " + temp_fmt + " " + temp_ncon);

            // Graph erzeugen
            // TODO : momentan nur einfacher Fall betrachtet, also ohne Gewichte -> fmt = -1 oder 0
            if (temp_fmt == -1 || temp_fmt == 0)
            {
                // Knoten anlegen
                for (int i = 0; i < temp_n; i++)
                    neuerKnoten(i);

                // Adjazenzlisten mit Kanten einlesen
                int von = -1;			// Startknoten jeder Kante der aktuellen Zeile (beginnen bei 1)
                while (zeile != null)
                {
                    zeile = datei.ReadLine();
                    // Bei Dateiende, Leer- oder Kommentarzeile die folgenden Schritten für diese Zeile überspringen
                    if (zeile == null || zeile == "" || zeile[0] == '%')
                        continue;

                    // zeile gültig, jetzt Adjazenzliste für den Knoten von+1 einlesen
                    von++;

                    // Zeile mit Adjazenzliste in einzelne Einträge aufsplitten
                    string[] kanten = zeile.Split(' ');
                    // anschließend jeden Eintrag in Kante umwandeln
                    for (int i = 1; i < kanten.Length; i++)
                    {
						// Knoten in Datei von 1 bis n, intern von 0 bis n-1 durch nummeriert
                        neueKante(von, Convert.ToInt32(kanten[i])-1, 0.0);
                    }
                    if (KnotenGrad < kanten.Length)
                        KnotenGrad = kanten.Length;
                }

                // zur Kontrolle nochmal erwartete und tatsächliche Knoten- und Kantenzahlen ausgeben
                Console.WriteLine("Anzahl Knoten " + v.Count + "/" + temp_n + "\t Anzahl Kanten " + M + "/" + temp_m);
            }


            return false;
        }
	}
}
